package com.排序.交换.快速;

import java.util.Arrays;

/**
 * the class of algorithm
 * <p>
 * 核心思想:
 * 分治法，
 * 在一趟排序中把将要排序的数据分成两个独立的部分，对这两部分进行排序使得其中一部分所有数据比另一部分都要小，然后继续递归排序这两部分，最终实现所有数据有序
 * <p>
 * .
 *
 * @author little_lunatic
 * @date 2022-12-09
 */
public class KS {
    public static void main(String[] args) {
        int[] arr = {9, 8, 0, 6, 10, 5, 4, 3, 2, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }


    public static void quickSort(int[] arry, int left, int right) {
        //运行判断，如果左边索引大于右边是不合法的，直接return结束次方法
        if (left >= right) {
            return;
        }
        int base = arry[left];
        //定义变量i，指向最左边
        int i = left;
        //定义j ,指向最右边
        int j = right;
        while (i != j) {
            //如果检索到比基准数大的或者相等的就停下
            while (arry[j] >= base && i < j) {
                j--;
            }
            while (arry[i] <= base && i < j) {
                i++;
            }
            //代码走到这里i停下，j也停下，然后交换i和j位置的元素
            int tem = arry[i];
            arry[i] = arry[j];
            arry[j] = tem;
        }
        arry[left] = arry[i];
        arry[i] = base;
        quickSort(arry, left, i - 1);
        quickSort(arry, j + 1, right);
    }
}
//[9, 8, 0, 6, 10, 5, 4, 3, 2, 1]
//[9, 8, 0, 6, 1, 5, 4, 3, 2, 10] 10和1交换
//[9, 8, 0, 6, 1, 5, 4, 3, 2, 10] 2和2交换， 外循环结束
//[2, 8, 0, 6, 1, 5, 4, 3, 9ij, 10] 9和2交换，arry[left] = arry[i], 因为 arr[i] 全都小于 9

//[2, 8i, 0, 6, 1j, 5, 4, 3, 9, 10] 递归开始排序 left - (i-1)
//[2, 1i, 0, 6, 8j, 5, 4, 3, 9, 10] 8和1交换
//[2, 1, 0ij, 6, 8, 5, 4, 3, 9, 10] 0和0交换， 外循环结束
//[0, 1, 2ij, 6, 8, 5, 4, 3, 9, 10] 2和0交换，arry[left] = arry[i], 因为 arr[i] 全都小于 9

//[0ji, 1, 2, 6, 8, 5, 4, 3, 9, 10] 递归开始排序 left - (i-1)
//[0ji, 1, 2, 6, 8, 5, 4, 3, 9, 10] 0和0交换，外循环结束，到这里递归 left - (i-1) 结束

//[0ji, 1, 2, 6, 8, 5, 4, 3, 9, 10] 递归开始排序  (j+1) - right
//[0ji, 1, 2, 6, 3i, 5, 4, 8j, 9, 10] 8,3交换
//[0ji, 1, 2, 6, 3, 5, 4ij, 8, 9, 10] 4,4交换 ,外循环结束
//[0ji, 1, 2, 4, 3, 5, 6ij, 8, 9, 10] 4,6交换

//[0ji, 1, 2, 4, 3ij, 5, 6, 8, 9, 10] 3，3交换
//[0ji, 1, 2, 3, 4ij, 5, 6, 8, 9, 10] 3，3交换